package com.douma.practice;


import com.douma.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class TreePath {

    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> allPath(TreeNode root) {
        dfs(root);
        return res;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;

        // 递的时候：将当前节点值加入到路径
        path.add(node.val);

        if (node.left == null && node.right == null) {
            res.add(new ArrayList<>(path));
        }

        dfs(node.left);
        dfs(node.right);

        // 回溯
        // 归的时候：将当前节点从当前路径中删除
        path.remove(path.size() - 1);
    }
}
